package 题目集.树.构建树;

import org.junit.Test;

public class 完全二叉树后序转前序 {
    int[] preOrder;
    int[] postOrder;
    int cnt;

    public int[] fun(int[] postOrder) {
        preOrder = new int[postOrder.length];
        this.postOrder = postOrder;
        cnt = postOrder.length - 1;
        build(0, postOrder.length - 1);
        return preOrder;
    }

    public void build(int start, int end) {
        if (start > end) return;
        preOrder[start] = postOrder[cnt--];
        int mid = start+end>>1;
        //这里给起点+1，是因为每次处理的都是起点，所以起点在下次递归中要变化
        build(mid + 1, end);    //这里和前序转后序的区别是，先处理右树，因为cnt是从右向左，即根右左
        build(start + 1, mid);
    }

    @Test
    public void test() {
        int[] postOrder = {1, 3, 2, 5, 7, 6, 4};
        int[] fun = fun(postOrder);
        for (int i : fun) {
            System.out.print(i + " ");
        }
    }
}
